/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date: A  April 2011
 */

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/local_type.hh"
#include "cpu/base.hh"

template<class Impl>
LocalTypeP<Impl>::LocalTypeP(DerivEdgeCPUParams *params)
    : BaseTypePredictor<Impl>(params, "Local"),
      localCtrBits(params->localCtrBits),
      localCtrs(this, (params->btypeTableMode == "AliasFree") ? 
              true : false),
      localPredictorSize(params->localPredictorSize),
      localHistoryTable(this, (params->btypeTableMode == "AliasFree") ? 
              true : false),
      localHistoryTableSize(params->localHistoryTableSize),
      localHistoryBits(params->localHistoryBits),
      blockShiftAmt(params->blockShiftAmt)
{
    if (params->btypeTableMode == "AliasFree") {
        tableMode = AliasFree;
    } else if (params->btypeTableMode == "Normal") {
        tableMode = Normal;
    } else {
        fatal("Invalid table mode for global type predictor.\n");
    }

    initVars();

    if (params->btypeLocalHysteresisMode == "Symmetric") {
        hysteresisMode = Symmetric;
    } else if (params->btypeLocalHysteresisMode == "Asymmetric") {
        hysteresisMode = Asymmetric;
    } else {
        fatal("Invalid hysteresis mode selected for local"
                " predictor\n");
    }
}

template<class Impl>
LocalTypeP<Impl>::~LocalTypeP()
{
    DPRINTF(EdgePredUnit,"Local destructed!\n");
}

template<class Impl>
void
LocalTypeP<Impl>::initVars()
{
    if (!isPowerOf2(localPredictorSize)) {
        fatal("Invalid local predictor size!\n");
    }

    if (tableMode == Normal) {
        /** Setup the array of counters for the local predictor */
        localCtrs.resize(localPredictorSize, PredictionTableEntry(this));

        for (int i = 0; i < localPredictorSize; ++i) {
            localCtrs[i].typeID = 0;
            localCtrs[i].hysteresis.setBits(localCtrBits);
        }
    }

    localPredictorMask = floorPow2(localPredictorSize) - 1;

    if (!isPowerOf2(localHistoryTableSize)) {
        fatal("Invalid local history table size!\n");
    }

    if (tableMode == Normal) {
        /** Setup the history table for the local table */
        localHistoryTable.resize(localHistoryTableSize,
                HistoryTableEntry(this));

        for (int i = 0; i < localHistoryTableSize; ++i) {
            localHistoryTable[i].hist = 0;
        }
    }

    /** Setup the history table for the local futrue file */
    localFutureFile.resize(Impl::MaxInFlightBlockNum);

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        localFutureFile[i].index = 0;
	localFutureFile[i].history = 0;
    }

    /** Setup the local history mask */
    localHistoryMask = (ULL(0x1) << localHistoryBits) - 1;
    localHistoryTableMask = floorPow2(localHistoryTableSize) - 1;

    DPRINTF(EdgePredUnit, "Local: size: %i, mask: %#x, "
            "counter size: %i, history length: %i, "
            "history mask: %#x, history table size: %i,"
            " mask: %#x.\n",
            localPredictorSize, localPredictorMask, 
            localCtrBits, localHistoryBits,
            localHistoryMask,
            localHistoryTableSize,
            localHistoryTableMask);

    threshold = (ULL(0x1) << (localCtrBits - 1)) - 1;
    threshold = threshold / 2;

    typeIdBits = floorLog2(TheISA::NumBranchType);

//    typeIdMask = static_cast<uint64_t>(typeIdBits) - 1;
    typeIdMask = (ULL(0x1) << typeIdBits) - 1;

    DPRINTF(EdgePredUnit, "LocalTypeP: type id bits: %i"
            " type id mask: %#x\n",
            typeIdBits, typeIdMask);
}

template<class Impl>
void
LocalTypeP<Impl>::reset()
{
    if (tableMode == Normal) {
        for (int i = 0; i < localPredictorSize; ++i) {
            localCtrs[i].typeID = 0;
            localCtrs[i].hysteresis.reset();
        }

        for (int i = 0; i < localHistoryTableSize; ++i) {
            localHistoryTable[i].hist = 0;
        }
    } else if (tableMode == AliasFree) {
        localCtrs.clear();
        localHistoryTable.clear();
    }
}

template<class Impl>
inline
uint64_t
LocalTypeP<Impl>::calcLocHistIdx(Addr &block_addr, int addr_space_ID)
{
    // Get low order bits after removing instruction offset.
    assert(addr_space_ID >= 0 && addr_space_ID <= 15);

    int reverse_as_id = ((addr_space_ID & 0x1) << 3)
                        | ((addr_space_ID & 0x2) << 1)
                        | ((addr_space_ID & 0x4) >> 1)
                        | ((addr_space_ID & 0x8) >> 3);

    uint64_t index = (block_addr >> blockShiftAmt) ^
           (reverse_as_id << (localHistoryBits - 4));

    if (tableMode != AliasFree) {
        index &= localHistoryTableMask;
    }

    return index;
}

template<class Impl>
inline
uint64_t
LocalTypeP<Impl>::calcLocPredIdx(Addr &block_addr, uint64_t history)
{
    uint64_t index = history ^ (block_addr >> blockShiftAmt);

    if (tableMode != AliasFree) {
        index &= localPredictorMask;
    }

    return index;
}

template<class Impl>
TheISA::BTypeID
LocalTypeP<Impl>::lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    BTypeID local_prediction = TheISA::InvalidExitType;
    uint64_t local_history_idx = 0;
    uint64_t local_history = 0;
    uint64_t local_predictor_idx = 0;

    LFFEntry lff_entry_new;

    //Get local history.
    local_history_idx = calcLocHistIdx(block_addr, addr_space_ID);
    local_history = localHistoryTable[local_history_idx].hist;

    if (block_id != oldest_block_id && oldest_block_id != 0) {
        BlockID tmp_bid = block_id; // latest block

        do {
            LFFEntry lff_entry;
            tmp_bid = (tmp_bid - 1) & 0x7;
            lff_entry = localFutureFile[tmp_bid];
            if (lff_entry.index == local_history_idx)
            {
                local_history = lff_entry.history;
                break;
            }
        } while (tmp_bid != (oldest_block_id & 0x7));
    }

    //Lookup local prediction
    local_predictor_idx = calcLocPredIdx(block_addr, local_history);
    local_prediction = localCtrs[local_predictor_idx].typeID;

    DPRINTF(EdgePredUnit,"Local: prediction = %i,"
            " for %#x.\n",
            local_prediction, block_addr);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    // Speculative update
    lff_entry_new.index = local_history_idx;
    lff_entry_new.history = ((local_history << typeIdBits) |
            (local_prediction & typeIdMask)) &
            localHistoryMask;

    localFutureFile[index] = lff_entry_new;

    return local_prediction;
}

template<class Impl>
TheISA::BTypeID
LocalTypeP<Impl>::update(BlockID block_id, Addr &block_addr, 
        int addr_space_id, BTypeID actual_type_id, ThreadID tid)
{
    uint64_t local_history_idx = 0;
    uint64_t local_predictor_hist = 0;
    uint64_t local_predictor_hist_new = 0;
    uint64_t local_predictor_idx = 0;

    assert(actual_type_id >= 0 && actual_type_id < TheISA::NumBranchType);

    local_history_idx = calcLocHistIdx(block_addr, addr_space_id);
    local_predictor_hist = localHistoryTable[local_history_idx].hist;

    //Update L1 tables
    local_predictor_hist_new = ((local_predictor_hist << typeIdBits) |
                               (actual_type_id & typeIdMask)) & localHistoryMask;

    localHistoryTable[local_history_idx].hist = local_predictor_hist_new;
    
    // Read and update L2 tables
    local_predictor_idx = calcLocPredIdx(block_addr, local_predictor_hist);
    BTypeID old_pred = localCtrs[local_predictor_idx].typeID;

    updateHysteresis(localCtrs[local_predictor_idx], actual_type_id);

    DPRINTF(EdgePredUnit,"Local: typeID = %i, old pred = %i.\n",
            actual_type_id,
            old_pred);

    return old_pred;
}

template<class Impl>
void
LocalTypeP<Impl>::squash(BlockID block_id, Addr block_pc, 
        BTypeID type_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    LFFEntry oldLFFEntry, newLFFEntry;
    oldLFFEntry = localFutureFile[index];
    newLFFEntry.index = oldLFFEntry.index;
    newLFFEntry.history = ((oldLFFEntry.history & (~typeIdMask)) |
            (type_id & typeIdMask))
            & localHistoryMask;
    localFutureFile[index] = newLFFEntry;

    DPRINTF(EdgePredUnit,"Local: Squashing BP to Block [bid:%i]"
            " due to misprediction.\n", block_id);
}

template<class Impl>
void
LocalTypeP<Impl>::squash(BlockID block_id, ThreadID tid)
{
    DPRINTF(EdgePredUnit, "Local: Squashing nothing due to fault?\n");
}

template<class Impl>
void
LocalTypeP<Impl>::updateHysteresis(PredictionTableEntry &entry,
        BTypeID actual_type_id)
{
    assert(actual_type_id >= 0 && actual_type_id < TheISA::NumBranchType);

    BTypeID current_type_id = entry.typeID;

    if (hysteresisMode == Symmetric) {
        if (entry.hysteresis.read() <= threshold) {
            entry.typeID = actual_type_id;
        }

        if (actual_type_id == current_type_id) {
            entry.hysteresis.increment();
        } else {
            entry.hysteresis.decrement();
        }
    } else if (hysteresisMode == Asymmetric) {
        if (entry.hysteresis.read() <= threshold) {
            entry.typeID = actual_type_id;
        }

        if (actual_type_id == current_type_id) {
            if (actual_type_id == TheISA::call ||
                    actual_type_id == TheISA::ret) {
                entry.hysteresis.increment((1 << localCtrBits) - 1);
            } else {
                entry.hysteresis.increment();
            }
        } else {
            if (actual_type_id == TheISA::call ||
                    actual_type_id == TheISA::ret) {
                entry.hysteresis.decrement((1 << localCtrBits) - 1);
            } else {
                entry.hysteresis.decrement();
            }
        }
    } else {
        panic("Invalid hysteresis mode selected.\n");
    }
}

